/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package uloha3;

import java.util.Arrays;
import java.util.List;

class VyriesDynamicky implements BatohAlgoritmus {

    List<Batoh> zoznamInstancii;
    int[][] pole;
    Cesty[][] poleCiest;

    public VyriesDynamicky(List<Batoh> zoznamInstancii) {
        this.zoznamInstancii = zoznamInstancii;
    }

    String vyriesJednuInstanciu(Batoh b) {
        int[] poleKonfiguracii = new int[b.pocetVeciVbatohu];
        Arrays.fill(poleKonfiguracii, 0);
        // Matica novePole = new Matica (b.pocetVeciVbatohu, b.maxHmotnost );
        pole = new int[b.pocetVeciVbatohu + 1][b.maxHmotnost + 1];
        poleCiest = new Cesty[b.pocetVeciVbatohu + 1][b.maxHmotnost + 1];
        
        //dalej zakomentovany kod tam nemusi byt, java pole inicializuje na nuly
//       for (int w = 0; w <= b.maxHmotnost; w++) {
//            pole[0][w] = 0;
//        }
//        for (int i = 0; i <= b.pocetVeciVbatohu; i++) {
//            pole[i][0] = 0;
//        }

        //inicializacia pola pre rekonstrukciu 
        for (int i = 0; i < poleCiest.length; i++) {
            for (int j = 0; j < poleCiest[i].length; j++) {
                poleCiest[i][j] = new Cesty(0, 0, true);
            }
        }

        for (int i = 1; i <= b.pocetVeciVbatohu; i++) {
            for (int w = 1; w <= b.maxHmotnost; w++) {
                //pre i = 1, ziskaj prvok 0 zo zoznamu veci v batohu
                int cenaAktualneSkumaneho = (int) b.zoznamVeci.get(i - 1).cenaVeci;
                int hmotnostAktualneSkumaneho = (int) b.zoznamVeci.get(i - 1).hmotnostVeci;
                if (hmotnostAktualneSkumaneho <= w) //dany predmet by sa zmestil (sam)do aktualneho batohu
                {
                    if ((cenaAktualneSkumaneho + pole[i - 1][w - hmotnostAktualneSkumaneho]) > pole[i - 1][w]) {
                        pole[i][w] = cenaAktualneSkumaneho + pole[i - 1][w - hmotnostAktualneSkumaneho];
                        poleCiest[i][w] = new Cesty(w - hmotnostAktualneSkumaneho, i - 1,true);
                    } else //pridanie predmetu nezlepsi max cenu 
                    {
                        pole[i][w] = pole[i - 1][w];
                        poleCiest[i][w] = new Cesty(w, i - 1,false);
                    }
                } else {
                    pole[i][w] = pole[i - 1][w];
                    poleCiest[i][w] = new Cesty(w, i - 1,false);
                }



            }//koniec pre vsetky mozne hmotnosti s danym poctom veci
        }//koniec pre vsetky veci v batohu

        int maxCena = pole[b.pocetVeciVbatohu][b.maxHmotnost];
        int i = b.pocetVeciVbatohu;
        int w = b.maxHmotnost;
        while (true) {
            if (i == 0 || w ==0) {
                break;
            }
            if (poleCiest[i][w].jeVbatohu)
                poleKonfiguracii[i - 1] = 1;
            else{
                poleKonfiguracii[i - 1] = 0;
            }
            int temp_i = poleCiest[i][w].predchodcaSuradnicaI;
            int temp_w = poleCiest[i][w].predchodcaSuradnicaW;
            i = temp_i;
            w = temp_w;
        }

        StringBuilder riesenie = new StringBuilder();
        riesenie.append(b.cisloInstancie + " " + b.pocetVeciVbatohu + " " + maxCena + " ");

        for (int index = 0; index < poleKonfiguracii.length; index++) {
            riesenie.append(poleKonfiguracii[index]);
        }
        riesenie.append("\n");
        return riesenie.toString();
    }

    public String vyriesProblemBatohu() {
        StringBuilder riesenieTotal = new StringBuilder();
        for (Batoh aktualnaInstancia : zoznamInstancii) {
            riesenieTotal.append(vyriesJednuInstanciu(aktualnaInstancia));
        }
        riesenieTotal.append("\n");
        System.out.println(riesenieTotal.toString());
        return riesenieTotal.toString();
    }

    private class Matica {

        int pocetVeci;
        int maxVahaVeci;
        int[][] pole;

        public Matica(int pocetVeci, int maxVahaVeci) {
            this.pocetVeci = pocetVeci;
            this.maxVahaVeci = maxVahaVeci;
            pole = new int[pocetVeci + 1][maxVahaVeci + 1];
        }

        @Override
        public String toString() {
            StringBuilder vypisMatice = new StringBuilder("\n");
            for (int i = 0; i < pole.length; i++) {
                for (int j = 0; j < pole[i].length; j++) {
                    vypisMatice.append(pole[i][j]);
                }
                vypisMatice.append("\n");
            }
            return vypisMatice.toString();
        }
    }

    private class Cesty {

        int predchodcaSuradnicaW;
        int predchodcaSuradnicaI;
        boolean jeVbatohu;

        public Cesty(int suradnicaW, int suradnicaI,boolean jeVbatohu) {
            this.predchodcaSuradnicaW = suradnicaW;
            this.predchodcaSuradnicaI = suradnicaI;
            this.jeVbatohu = jeVbatohu;
        }
    }
}
